package com.person.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 76.最小覆盖子串
 * 2023-03-27 16:33:33
 **/
public class Sequence_0076_MinimumWindowSubstring {

    public static void main(String[] args) {
        Solution solution = new Sequence_0076_MinimumWindowSubstring().new Solution();
        solution.minWindow("ADOBECODEBANC", "ABC");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String minWindow(String s, String t) {

            HashMap<Character, Integer> tMap = new HashMap<>();
            HashMap<Character, Integer> sMap = new HashMap<>();
            for (char c : t.toCharArray()) {
                tMap.put(c, tMap.getOrDefault(c, 0) + 1);
            }

            int l = 0, r = -1;
            int minL = -1, minR = -1, min = Integer.MAX_VALUE;

            while (r < s.length()) {
                r++;
                if (r<s.length()) {
                    sMap.put(s.charAt(r), sMap.getOrDefault(s.charAt(r), 0) + 1);
                }
                while (l <= r && check(tMap, sMap)) {
                    if (min > r - l + 1) {
                        minL = l;
                        minR = r;
                        min = r - l + 1;
                    }
                    sMap.put(s.charAt(l), sMap.get(s.charAt(l)) - 1);
                    l++;
                }

            }

            return minR == -1?"":s.substring(minL, minR + 1);
        }

        //判断是否包含
        boolean check(Map<Character, Integer> tMap, Map<Character, Integer> sMap) {
            if (sMap.size() == 0) return false;
            Iterator<Character> tIter = tMap.keySet().iterator();
            while (tIter.hasNext()) {
                Character key = tIter.next();
                if (tMap.get(key) > sMap.getOrDefault(key, 0)) {
                    return false;
                }
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}